class Solution:

    def isMatch(self, s: str, p: str, s_i=None, p_i=None) -> bool:
        if s_i is None:
            s_i = len(s) - 1
        if p_i is None:
            p_i = len(p) - 1
        if s_i == -1 and p_i == -1:
            return True
        if s_i == -1 and p[p_i] == '*' and p_i >= 1:
            return self.isMatch(s, p, s_i, p_i - 2)
        if s_i < 0 or p_i < 0:
            return False
        if p[p_i] == '.':
            return self.isMatch(s, p, s_i - 1, p_i - 1)
        if p[p_i] != '*':
            if p[p_i] == s[s_i]:
                return self.isMatch(s, p, s_i - 1, p_i - 1)
            else:
                return False

        k = 0
        while k <= s_i+1:
            if k == 0 or p[p_i - 1] == s[s_i - k+1] or p[p_i - 1] == '.':
                if self.isMatch(s, p, s_i - k, p_i - 2):
                    return True
                k += 1
            else:
                return False
        return False


if __name__ == '__main__':
    so = Solution()
    # s = "iss"
    # p = "is*"
    s = "mississippi"

    p = "mis*is*ip*."
    r = so.isMatch(s, p)
    print(r)
